#pragma once

#include "my_defs.h"

typedef struct my_rbtree_node_s my_rbtree_node_t;

struct my_rbtree_node_s {
    my_rbtree_node_t    *left;
    my_rbtree_node_t    *right;
    my_rbtree_node_t    *parent;
    u_char              color;
};

typedef struct my_rbtree_s my_rbtree_t;

typedef int (*my_rbtree_node_cmp_pt) (my_rbtree_node_t *a,
    my_rbtree_node_t *b);

struct my_rbtree_s {
    my_rbtree_node_t        *root;
    my_rbtree_node_t        *sentinel;
    my_rbtree_node_cmp_pt   cmp;
};

#define my_rbtree_init(tree, s, c)                          \
    my_rbtree_sentinel_init(s);                             \
    (tree)->root = s;                                       \
    (tree)->sentinel = s;                                   \
    (tree)->cmp = c

void my_rbtree_insert(my_rbtree_t *tree, my_rbtree_node_t *node);
void my_rbtree_delete(my_rbtree_t *tree, my_rbtree_node_t *node);
my_rbtree_node_t *my_rbtree_lookup(my_rbtree_t *tree, my_rbtree_node_t *target);
my_rbtree_node_t *my_rbtree_ge(my_rbtree_t *tree, my_rbtree_node_t *target);
my_rbtree_node_t *my_rbtree_le(my_rbtree_t *tree, my_rbtree_node_t *target);

#define my_rbt_red(node)               ((node)->color = 1)
#define my_rbt_black(node)             ((node)->color = 0)
#define my_rbt_is_red(node)            ((node)->color)
#define my_rbt_is_black(node)          (!my_rbt_is_red(node))
#define my_rbt_copy_color(n1, n2)      (n1->color = n2->color)

/* a sentinel must be black */
#define my_rbtree_sentinel_init(node)  my_rbt_black(node)

static inline my_bool_t
my_rbtree_empty(my_rbtree_t *tree) {
    return tree->root == tree->sentinel;
}

static inline my_rbtree_node_t *
my_rbtree_min(my_rbtree_node_t *node, my_rbtree_node_t *sentinel) {
    if (node == sentinel) {
        return sentinel;
    }

    while (node->left != sentinel) {
        node = node->left;
    }

    return node;
}

static inline my_rbtree_node_t *
my_rbtree_max(my_rbtree_node_t *node, my_rbtree_node_t *sentinel) {
    if (node == sentinel) {
        return sentinel;
    }

    while(node->right != sentinel) {
        node = node->right;
    }

    return node;
}

my_rbtree_node_t *my_rbtree_next(my_rbtree_t *tree, my_rbtree_node_t *node);

#define my_rbtree_data(node, type, link)                                          \
    (type *) ((u_char *) node - offsetof(type, link))
